/*
 * @lc app=leetcode.cn id=4 lang=java
 *
 * [4] 寻找两个正序数组的中位数
 * 
 * 算法的时间复杂度应该为 O(log (m+n))
 */

// @lc code=start
class Solution {
	// 二分查找法 ??

	// 优化的直接查取中间值方法， 时间复杂度还是 O(m+n)
	// [1ms, 100%], [42.2MB, 55%]
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int len1 = nums1.length, len2 = nums2.length;
		int len = nums1.length + nums2.length;
		int half = len / 2, index1 = 0, index2 = 0;
		int pre = 0, next = 0;
		for (int index = 0; index <= half; index++) {
			pre = next;
			if (index1 == len1) {
				next = nums2[index2];
				index2++;
			} else if (index2 == len2) {
				next = nums1[index1];
				index1++;
			} else if (nums1[index1] < nums2[index2]) {
				next = nums1[index1];
				index1++;
			} else {
				next = nums2[index2];
				index2++;
			}
		}
		return len % 2 == 1 ? next : (pre + next) / 2.0;
	}
}
// @lc code=end

// // 解题思路：
// 	// 直接按照序列排序，组成一个新的数组，取中间值
// 	// 这种时间复杂度为 O（m+n)，不符合题中要求，虽然提交最终的答案能成功
// 	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 		int len1 = nums1.length, len2 = nums2.length;
// 		int len = len1 + len2;
// 		int[] nums = new int[len];
// 		int index1 = 0, index2 = 0;
// 		for (int i = 0; i < len; i++) {
// 			if (index1 < len1 && index2 < len2) {
// 				nums[i] = nums1[index1] < nums2[index2] ? nums1[index1++] : nums2[index2++];
// 			} else if (index1 < len1) {
// 				nums[i] = nums1[index1++];
// 			} else if (index2 < len2) {
// 				nums[i] = nums2[index2++];
// 			}
// 		}
// 		if (len % 2 == 1)
// 			return nums[len / 2];
// 		else
// 			return (nums[len / 2 - 1] + nums[len / 2]) / 2.0f;
// 	}